Liverpool bổ nhiệm Gérard Houllier làm đồng huấn luyện viên trưởng cùng với Evans cho mùa giải 1998-99. Những kết quả tệ hại khiến áp lực đè nặng hai người và thất bại 3–1 trước Tottenham Hotspur ở League Cup là giọt nước tràn ly khiến Evans ra đi.[58] Trận đấu đầu tiên của Houllier trong vai trò huấn luyện viên toàn quyền là thất bại 3–1 trước Leeds United.[59] Phong độ của Liverpool không cải thiện nhiều dưới thời Houllier khi đội bóng bị loại sớm tại Cúp UEFA và Cúp FA, chỉ về thứ bảy ở giải Ngoại hạng và mất suất dự cúp châu Âu mùa sau.[60] Houllier làm mới đội hình trong mùa bóng 1999-2000. Ông đem về các tân binh người nước ngoài như Dietmar Hamann, Sami Hyypiä và Sander Westerveld; David James, Ince và McManaman là những người ra đi.[61] Houllier tiếp tục công cuộc cải cách với bản hợp đồng kỷ lục Emile Heskey trị giá 11 triệu bảng vào tháng 3.[62] Liverpool thất bại trong việc tìm đường trở lại UEFA Champions League khi chỉ cán đích thứ tư. Họ cũng thi đấu không tốt ở Cúp FA và League Cup khi đều bị loại sớm.[63]

Vào mùa giải 2000-01 Liverpool giành cú ăn ba danh hiệu độc nhất vô nhị. Danh hiệu đầu tiên là League Cup khi họ thắng Birmingham City 5–4 trong loạt sút luân lưu sau khi hai đội hòa nhau 1-1.[64] Họ tiếp tục vô địch Cúp FA khi Owen ghi hai bàn trong mười phút giúp đội bóng vượt qua Arsenal với tỉ số 2–1.[65] Danh hiệu cuối cùng là Cúp UEFA khi bàn bàn phản lưới nhà trong hiệp phụ của Delfí Geli giúp họ giành chiến thắng 5–4 trước Alavés của Tây Ban Nha.[66] Liverpool về thứ ba tại giải vô địch quốc gia và chính thức trở lại với giải đấu hàng đầu châu Âu UEFA Champions League lần đầu tiên kể từ Thảm họa Heysel.[67] UEFA Champions League mùa giải 2001–02 chứng kiến đội bóng đi tới vòng tứ kết, nơi họ bị Bayer 04 Leverkusen của Đức loại với tổng tỉ số 4–3.[68] Đây là mùa giải tốt nhất của Liverpool trong nhiều năm trở lại đây khi họ về thứ nhì giải Ngoại hạng với bảy điểm kém hơn so với nhà vô địch Arsenal.[69] Mặc dù vậy Liverpool không thể bảo vệ thành công chức vô địch Cúp FA và League Cup khi lần lượt bị loại ở vòng bốn và vòng ba.[70] Vấn đề sức khỏe của Houllier cũng là một nét buồn của mùa giải. Ông lên cơn đau tim trong thời gian nghỉ giữa hiệp trong trận đấu với Leeds tại Anfield. Ông phải trải qua ca mổ dài 11 tiếng đồng hồ để phẫu thuật lại động mạch chủ và chỉ trở lại vào tháng 2. Trợ lý Phil Thompson là người tạm thời cầm quân.[71]

Houllier mua về thêm nhiều cầu thủ cho mùa bóng 2002–03, trong đó có Bruno Cheyrou, Salif Diao và El Hadji Diouf. Cheyrou được chọn thay cho Nicolas Anelka, người có màn thể hiện không tồi khi chuyển tới theo dạng cho mượn từ Paris Saint-Germain ở mùa giải trước.[72] Liverpool bất bại trong 12 trận đầu tiên mùa giải và đứng đầu bảng xếp hạng với cách biệt 7 điểm.[73] Thất bại trước Middlesbrough ở trận đấu sau đó khởi đầu chuỗi 12 trận không biết mùi chiến thắng cho tới khi họ vượt qua Southampton 1–0 vào tháng 1.[74] Câu lạc bộ kết thúc mùa giải ở vị trí thứ năm. Mặc dù bị loại sớm ở Cúp FA và UEFA Champions League, Liverpool vẫn vô địch Cúp Liên đoàn khi hạ Manchester United trong trận chung chung kết.[75] Mùa giải 2003-04 bắt đầu khá muộn màng khi Liverpool thua trận đấu tiên của mùa giải với tỉ số 2–1 trước Chelsea.[76] Kết thúc năm 2003 họ thua 6 trong số 18 trận ở giải Ngoại hạng.[77] Trong nửa sau của mùa giải họ chỉ thua thêm có bốn trận và có suất dự UEFA Champions League 2004-05 với vị trí thứ 4.[78] Họ đều bị loại ở Cúp UEFA và League Cup. Ở Cúp FA, họ bị Portsmouth vượt qua với tỉ số 1–0 trong trận đá lại vòng 5.[79] Cuối mùa giải đó Houllier được thay thế bởi Rafael Benítez.[80]

Trong mùa giải 2004-05 họ bị đội hạng dưới Burnley loại ngay từ vòng ba Cúp FA.[81] Câu lạc bộ lọt vào chung kết League Cup nhưng thua 3-2 trước Chelsea.[82] Liverpool cũng lọt vào chung kết UEFA Champions League. Họ bị A.C. Milan của Ý dẫn trước 3–0 ngay trước giờ nghỉ, tuy nhiên ba bàn thắng trong vòng 6 phút giúp Liverpool gỡ hòa 3–3. Hiệp phụ không có thêm bàn thắng nào được ghi đồng nghĩa với việc trận đấu bước vào loạt luân lưu, nơi Liverpool thắng 3–2.[83] Việc chỉ đứng thứ 5 ở giải Ngoại hạng khiến đội bóng không thể dự Champions League mùa sau cũng như không thể bảo vệ ngôi vương. UEFA sau đó cho phép họ tham dự, nhưng là từ vòng loại thứ nhất.[84] Tại giải đấu mà họ là đương kim vô địch, Liverpool bị loại bởi đội bóng Bồ Đào Nha Benfica tại vòng loại trực tiếp thứ nhất.[85] Ở mùa bóng 2005-06 họ đứng ở vị trí thứ ba. Họ lọt vào Chung kết Cúp FA 2006 gặp West Ham United. Liverpool thắng 3–1 trong loạt luân lưu 11m sau khi trận đấu kết thúc với tỉ số hòa 3–3.[86]